package chapter04_RecursionAndDynamic.feibona;

/**
 * 描述：
 *
 * @author hl
 * @date 2021/6/3 9:29
 */
public class Feibona {
    public static void main(String[] args) {
        Feibona f = new Feibona();
        int n = 10;
        System.out.println(f.fl(n));
        System.out.println(f.fl2(n));
    }
    /**
     * 动态规划，时间复杂度O(n)
     * @param n
     * @return
     */
    public int fl(int n){
        if (n < 1) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return 1;
        }
        int f = 1, s = 1, temp = 0;
        for (int i = 3; i <= n; i++) {
            temp = f + s;
            f = s;
            s = temp;
        }
        return s;
    }

    /**
     * 一个二阶递推数列，一定可以矩阵乘法的形式表示，且矩阵为2*2矩阵
     * (f(n), f(n - 1)) = (f(n - 1), f(n - 2)) * ([[1, 1], [1, 0]] ^ (n - 2))
     * 重点在于如何快速求出base矩阵的幂，快速求幂的过程时间复杂度可以达到log(N)
     * @param n
     * @return
     */
    public int fl2(int n){
        if (n < 1) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return 1;
        }
        int[][] base = {{1,1},{1,0}};
        int[][] res = MatrixPower.matrixPower(base, n - 2);
        return res[0][0] + res[1][0];
    }


}
